package com.leetcode.August;

/**
 * @Description: 45. 跳跃游戏 II
 * @Author: Mr.Fxy
 * @CreateTime: 2024-08-05 22:07
 */
public class LC45跳跃游戏II {
    public int jump(int[] nums) {
        int n = nums.length;
        int maxPos = 0; // 当前跳跃能到达的最远下标 索引
        int next = 0; // 下次跳跃能到达的最远下标 索引位置
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (i > maxPos) {// 超过了当前跳跃的最远距离，需要再跳一次
                maxPos = next;//上一步跳跃所能达到的最远索引。
                next = 0;//准备下一次跳跃。
                ++res;//又多了一次跳跃
            }
            next = Math.max(next, nums[i] + i);
        }
        return res;
    }
//    public int jump2(int[] nums) {
//        int n = nums.length;
//        int maxPos = 0;
//        int next = 0;
//        int res = 0;
//        for (int i = 0; i < n; ++i) {
//            if (i > maxPos) {
//                maxPos=next;
//                next=0;
//                ++res;
//            }
//          next=Math.max(next,nums[i]+i);
//        }
//        return res;
//    }
}
